﻿public class Solution102
{
    public IList<IList<int>> LevelOrder2(TreeNode root)
    {
        IList<IList<int>> res = new List<IList<int>>();

        IList<TreeNode> queue = new List<TreeNode>();

        if (root != null)
        {
            queue.Add(root);
        }//root null 为空，直接达成条件queue.Count ==0

        while (queue.Count > 0)//终止条件
        {
            //要把当前队列里面的全部遍历（当前层）
            IList<int> temp = new List<int>();
            for (int i = 0; i < queue.Count; i++)
            {

                TreeNode first = queue[i];


                Console.WriteLine(first.val);
                //把根节点记录下来
                temp.Add(first.val);
                //出队，列表的第一个元素
                queue.Remove(first);

                //把孩子入队伍
                queue.Add(first.left);
                queue.Add(first.right);

            }
            res.Add(temp);

        }
        return res;

    }
    //recursion(queue, res)
    public IList<IList<int>> LevelOrder(TreeNode root)
    {
        IList<IList<int>> res = new List<IList<int>>();

        Queue<TreeNode> queue = new Queue<TreeNode>();

        if (root != null)
        {
            queue.Enqueue(root);
        }//root null 为空，直接达成条件queue.Count ==0

        while (queue.Count > 0)//终止条件
        {
            //要把当前队列里面的全部遍历（当前层）
            IList<int> temp = new List<int>();
            int queueLen = queue.Count;
            for (int i = 0; i < queueLen; i++)

            {
                //出队，列表的第一个元素

                TreeNode first = queue.Dequeue();



                //把根节点记录下来
                temp.Add(first.val);


                //把孩子入队伍
                if (first.left != null)
                {
                    queue.Enqueue(first.left);
                }
                if (first.right != null)
                {
                    queue.Enqueue(first.right);
                }



            }
            res.Add(temp);

        }
        return res;

    }


}
class Program102
{

    static void Main102(string[] args)
    {
        Console.WriteLine("层序遍历结果：");

        // 创建二叉树示例
        TreeNode root = new TreeNode(1);
        root.right = new TreeNode(2);
        root.right.left = new TreeNode(3);

        // 创建 Solution 实例并调用 InorderTraversal 方法
        Solution102 solution = new Solution102();
        IList<IList<int>> result = solution.LevelOrder(root);


        // 打印遍历结果
        Console.WriteLine("层序遍历结果：");
        foreach (IList<int> num in result)
        {
            foreach (int i in num)
            {
                Console.WriteLine(i);
            }

        }
    }

}